package leetcode_700;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *MaximumProductOfThreeNumbers_628 寻找一个数组里三个元素相乘的最大乘积
 *describe:调整两个堆  AC 100%
 *2018年9月20日 上午10:32:32
 */
public class MaximumProductOfThreeNumbers_628 {
	public static void main(String[] args) {
		PriorityQueue<Integer> queue=new PriorityQueue<>(2);
		queue.offer(2);
		queue.offer(4);
		queue.offer(3);
		queue.offer(5);
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
	}
	
	/**
	 * describe:手写最小堆和最大堆的调整 AC 100%
	 * 2018年9月20日 上午10:32:15
	 */
	public int maximumProduct(int[] nums) {
        int[] heap=new int[3];//正数堆
        int[] _heap=new int[2];//负数堆
        for(int i=0;i<3;++i) {
        	heap[i]=nums[i];
        }
        Arrays.sort(heap);
        _heap[0]=heap[0];
        _heap[1]=heap[1];
        for(int i=3;i<nums.length;++i) {
        	if(nums[i]>heap[0]) {//调整堆
        		heap[0]=nums[i];
        		Arrays.sort(heap);
        	}
        	if(nums[i]<_heap[1]) {//比负数堆的最大还小
        		if(nums[i]<_heap[0]) {
        			_heap[1]=_heap[0];
        			_heap[0]=nums[i];
        		}
        		else {
        			_heap[1]=nums[i];
        		}
        	}
        }
        int res=1;
        for(int i=0;i<3;++i) {
        	res*=heap[i];
        }
        return Math.max(res, heap[2]*_heap[0]*_heap[1]);
    }

}
